BZOJ2187 fraction <类欧几里得>

Problem

fraction

Description

给出个正整数，求一个最简分数满足。
若有多组解，输出最小的一组，若仍有多组解，输出最小的一组。

Input

本题有多组数据，有若干行，每行个数。以文件的末尾作为结束。

Output

对于输入的每组数据输出一个最简分数。

Sample Input

1 3 1 2
2 1 3 1
2 1 4 1
1000 1001 1001 1002

Sample Output

HINT

对于的数据,
数据保证至少存在一个最简分数符合条件。

标签：类欧几里得

Solution

类欧几里得基础题。

设为满足的，考虑将其转化为规模更小的问题。

若和间相差至少一个整数，则为最小符合条件的整数，为
若，则一定有等价不等式，于是将问题转化为，求出后颠倒分子分母得到
若或，令，则有，问题转化为，求出后即可还原出

由于每次均将参数变为其辗转相模的结果，故而复杂度和欧几里得算法大致相同。

Code

#include <bits/stdc++.h>
using namespace std;
typedef double dnt;
typedef long long lnt;
lnt gcd(lnt x, lnt y) {return y ? gcd(y, x%y) : x;}
lnt flr(lnt x, lnt y) {return (lnt)floor((dnt)x/(dnt)y);}
lnt cel(lnt x, lnt y) {return (lnt)ceil((dnt)x/(dnt)y);}
void getans(lnt a, lnt b, lnt c, lnt d, lnt &p, lnt &q) {
    if (flr(a, b)+1 <= cel(c, d)-1) p = flr(a, b)+1, q = 1;
    else if (!a) p = 1, q = flr(d, c)+1;
    else if (a <= b && c <= d) getans(d, c, b, a, q, p);
    else {lnt k = a/b; getans(a-b*k, b, c-d*k, d, p, q), p += q*k;}
}
int main() {
    lnt a, b, c, d, p, q, t;
    while (~scanf("%lld%lld%lld%lld", &a, &b, &c, &d))
        t = gcd(a, b), a /= t, b /= t, 
        t = gcd(c, d), c /= t, d /= t, 
        getans(a, b, c, d, p, q), 
        printf("%lld/%lld\n", p, q);
    return 0;
}